\chapter{O protocolo}
\label{cap:proto}

Neste trabalho desenvolvemos uma variação de protocolo \textit{Token Ring} sem fio para MANet. 
Esse protocolo consiste em anel de anéis em que vários anéis se penduram a um anel varal.
Um varal é um anel formado por nós coordenadores de todos anéis pendurados a ele.

Este protocolo tem por objetivos:
\begin{itemize}
 \item prover uma solução para que diferentes anéis pendurados a um mesmo varal possam fazer 
troca de informações (pacotes)
 \item reduzir consumo de energia
\end{itemize}

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.6]{anel-de-aneis.pdf}
\caption{Anel de anéis}
\label{fig:aneldeaneis}
\end{figure}

\section{A descrição do protocolo}
\label{sec:descricao}
Neste protocolo classificamos um nó de seguinte forma:
\begin{itemize}
 \item simples - um nó comum, sem privilégios
 \item proprietário - criador de anel ou eleito para ser dono de anel
 \item anel unitário - aquele em que um nó é predecessor e sucessor de si mesmo
 \item varal - é um anel especial onde os anéis comuns se penduram
 \item coordenador - representante de um anel em um varal
 \item líder - criador de varal ou eleito para ser proprietário de varal
\end{itemize}

Em um varal cada coordenador possui um predecessor e um sucessor, ambos coordenadores de dois
anéis diferentes. Assim, cada coordenador terá dois predecessores e dois sucessores. Por 
exemplo, o nó Y (coordenador no anel B) na figura \ref{fig:aneldeaneis} tem por predecessores
o nó C (membro do anel B) e o nó H (também coordenador), e tem por sucessores o nó B (membro
do anel B) e o nó D (também coordenador).

Neste protocolo dividimos o roteamento em dois, à saber: roteamento intra-anel e inter-anel.
O roteamento intra-anel é o roteamento entre estações que pertencem ao mesmo anel, por exemplo
o roteamento no anel S da figura \ref{fig:aneldeaneis}. E o roteamento entre os coordenadores
é denominado roteamento inter-anel.

\section{Definições formais}
Sejam
\begin{itemize}
 \item $R_{X}$ anel do nó $X$ 
 \item $Pred_{X}$ predecessor do nó $X$
 \item $Succ_{X}$ sucessor do nó $X$
 \item $L_{IDs}$ lista de identificadores
 \item $S_{IDsX}$ sequência de IDs (exceto $X$) de nós no $R_{X}$
 \item $xP_{X}$ ex-predecessor do nó $X$
 \item $xS_{X}$ ex-sucessor do nó $X$
 \item $T_{R_{X}}$ tabela de conectividade do nó X associado ao anel $R$
 \item $T_{V_{X}}$ tabela de conectividade do nó X associado ao varal $V$
 \item $L_{X}$ lista de nós que o $X$ consegue escutar, mas que não compartilham 
anel com $X$ 
\end{itemize}


Cada coordenador possui uma $L_{IDs}$ de todos os nós em seu anel.
Esses identificadores podem facilitar o encaminhamento de dados entre anéis através de varal.
Explicando o conceito com o exemplo da figura \ref{fig:aneldeaneis}: se o destinatário 
(por exemplo, nó U) não pertencer ao mesmo anel que o remetente (por exemplo, nó L), os dados
são encaminhados do remetente L para o seu coordenador D, deste para o coordenador seguinte,
e assim sucessivamente até o coordenador F e deste último para o destinatário U.

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{varal-p.pdf}
\caption{Varal construído}
\label{fig:varal}
\end{figure}

Na construção de um anel de anéis, a primeira tarefa é a construção de varal~\ref{fig:varal}
através de inclusão de nós até que a capacidade máxima deste varal seja atingida. Porém,
se um nó solicitar inclusão no varal em construção, e não for alcançável por pelo 
menos dois nós sucessivos no varal, então:

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{novo-anel-pendurado-varal.pdf}
\caption{Anel R pendurado no varal}
\label{fig:anelpendurado}
\end{figure}

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{novo-anel-nao-pendurado-varal.pdf}
\caption{Anel unitário R}
\label{fig:anelnaopendurado}
\end{figure}

\begin{itemize}
 \item ou esse nó vai pendurar em um nó no varal (caso ele for alcançável por algum nó no varal)
formando um anel com dois nós~\ref{fig:anelpendurado};
 \item ou ele forma um anel unitário
~\ref{fig:anelnaopendurado};
\end{itemize}

\section{Estrutura de \textit{token}}
A formação de um anel requer que um \textit{token} seja criado por algum nó. Em um anel unitário,
o \textit{token} não circulará até que um outro nó junte ao anel.

Na figura ~\ref{fig:aneldeaneis} ilustramos uma estrutura que representa um anel de anéis com
a capacidade fixa em seis estações por anel. Nessa estrutura, o anel V representa o varal - 
o primeiro anel criado. Na seção \ref{sec:transanelemvaral} apresentaremos a estratégia de 
transformar um anel em varal.

\begin{table}[!hc]
\centering
		\begin{tabular}[c]{|c|c|c|c|c|c|c|c|c|} 
			\hline 
			FC & RA & DA & SA & NoN & Cnt\_Gen & Cnt\_Coord & Seq\\ 
			\hline
		\end{tabular}
           \caption[Short]{Quadro do Token de anel}
\label{tab:tokendepermissao}
\end{table}

A estrutura de \textit{token} padrão no nosso protocolo \ref{tab:tokendepermissao} não difere muito da
estrutura de \textit{token} \ref{tab:quadrotoken} apresentada na seção \ref{sec:protocolo}. A seguir,
descrevemos os campos de \textit{token} de permissão:

O campo FC identifica o tipo de \textit{token} (\textit{token} de permissão, ``Atribuir predecessor'',
``Atribuir sucessor'', etc). O campo RA informa o
endereço do anel a que o \textit{token} pertence, DA é o endereço do nó que vai receber o \textit{token}; SA
é o endereço do nó que envia o \textit{token}, o campo Seq representa o número de sequência no \textit{token},
é inicializado em zero e incrementado por cada nó que recebe e passa o \textit{token} adiante. O campo 
Cnt\_Gen pode ser lido por um nó qualquer em um anel, porém somente o proprietário desse anel poderá
incrementá-lo. O campo Cnt\_Coord pode ser lido por um nó qualquer em um anel, porém somente o coordenador
do anel poderá incrementá-lo. Tanto o campo Cnt\_Gen como o campo Cnt\_Coord são inicializados em zero e o
primeiro é incrementado cada vez que o \textit{token} passa pelo proprietário, ao passo que o segundo é
incrementado cada vez que o \textit{token} passa pelo coordenador. E, o campo NoN é designado a número
atual de nós em anel, ele é determinado pela diferença entre Seq atual e Seq anterior. 
\underline{\textbf{Observação:}} o \textit{token} de varal tem a mesma estrutura que o \textit{token}
apresentado na figura \ref{tab:tokendepermissao} a excessão do campo Cnt\_Coord (que não tem necessidade
de existir em varal).

%Gerenciamento de comunicação
\section{Comunicação entre anéis}
Cada nó deve manter uma $L_{IDs}$ de todos os nós no anel (exceto varal) a qual ele faz parte.
Para que isso seja possível, quando um nó $X$ entra em $R_{X}$, seja $X$ um coordenador ou nó
comum, o sucessor do $X$ gera e transmite um aviso de inclusão (com ID do nó $X$) para o sucessor
dele; deste último para o sucessor dele, e assim sucessivamente até que o aviso chegue ao
predecessor do nó $X$. Logo, este predecessor envia uma $S_{IDsX}$ para o nó $X$.
Também, quando um nó $X$ deixa $R_{X}$, seja $X$ um coordenador ou nó
comum, $xS_{X}$ gera e transmite um aviso de saída (com ID do nó $X$) para o sucessor
dele; deste último para o sucessor dele, e assim sucessivamente até que o aviso chegue ao
$xP_{X}$.

Se um nó $X$ cair inesperadamente, o $xP_{X}$ procura na tabela de conectividade
um nó para fechar o anel. Feito isso, $xP_{X}$ gera e envia um \textit{token} de reapresentação
contendo ID dele para o sucessor. Quando um nó receber um \textit{token} de reapresentação com
identificador ID do seu predecessor, ele registra esse ID na $L_{IDs}$, então 
retransmite o \textit{token} de reapresentação recebido, e, gera e envia um \textit{token} de 
reapresentação com ID dele para o sucessor dele. Se o \textit{token} de reapresentação recebido tiver
ID de outro nó (diferente de predecessor e dele mesmo), ele registra esse ID na $L_{IDs}$, e 
retransmite o \textit{token} de reapresentação recebido. E, se receber um \textit{token} de
reapresentação com ID dele mesmo, ele não retransmite esse \textit{token}.


\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.45]{anel-e-lista-de-ids.pdf}
\caption{Lista de ids em C}
\label{fig:listaid}
\end{figure}

\section{Gerenciamento de conectividade}
Cada nó possui mecanismos para fazer gerenciamento de conexão. Para gerenciar uma conexão cada
nó mantém tabela(s) de conectividade. Uma tabela de conectividade permite a um determinado nó
$X$ registrar as transmissões escutadas com origem em nós que ele consegue escutar. Esses nós podem
estar no mesmo anel que ele ou não: para os nós no seu anel, ele mantém uma tabela ordenada 
$T_{R_{X}}$ ao passo que para os nós fora do seu anel, ele mantém uma tabela não ordenada
$L_{X}$. A ordem crescente aplicada às tabelas de conectividade corresponde a número
de sequência (Seq) no \textit{token}.
Ademais, salientamos que cada coordenador $X$ possue três tabelas de conectividade,
$T_{R_{X}}$, $T_{V_{X}}$, e $L_{X}$.

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{varal-tab-conect.pdf}
\caption{Alcance de sinal e tabelas de conectividade do H}
\label{fig:alcance}
\end{figure}

Na figura ~\ref{fig:alcance}, apresentamos um exemplo de área de transmissão e tabelas de
conectividade de um nó coordenador.
Consideremos o varal V (relacionado a tabela 2): Quando o \textit{token} sai do nó R o Seq vale 1, 
depois o nó H vai escutar uma próxima transmissão somente quando o \textit{token} sair do T, nesse
instante Seq valerá 3. Então, H deduzirá que houve uma transmissão entre R e T que ele
não conseguiu escutar. Quando Q transmitir o \textit{token}, H verifica que Seq vale 5, então
deduzirá que houve uma transmissão entre T e Q que ele não conseguiu novamente escutar.
Da mesma forma, no anel K (relacionado a tabela 1), H escuta uma transmissão partindo do
I com Seq igual a 1, e mais tarde volta a escutar uma transmissão partindo do nó L com
Seq valendo 4, então conclui que houve duas transmissões que não conseguiu escutar. Na
tabela 3, o nó H registra os nós que ele consegue escutar (P e B), porém estes estão fora
dos seus anéis. O nó P está no anel A e o B está no anel E.

%Aproveitar e falar de ack implicito.
Nas redes de telecomunicações é muito importante que uma estação receptora confirme
as mensagens. Normalmente, quando uma estação recebe uma mensagem ele transmite uma resposta
ao emissor avisando o recebimento da mensagem. No nosso protocolo, seguindo a idéia em 
\cite{ergenthesis}, adotamos o conceito \emph{ACK} (resposta de reconhecimento positivo 
de mensagem~\cite{kurose}) implícito - \emph{AckI}. Isto é, o
processo em que um nó transmite um \textit{token} e monitora esse \textit{token} até que seja retransmitido
pelo sucessor dele.

%Coordenador e proprietário
Dividimos as tarefas de gerenciamento de um anel entre o proprietário e o coordenador.
O proprietário é a estação cujo identificador é RA, e o coordenador é a estação que
representa uma ``porta'' do anel para um varal e vice-versa. Por exemplo, a estação H é
o coordenador do anel K na figura \ref{fig:alcance}. Conforme mencionado anteriomente, um
proprietário é a estação que cria o seu anel ou, é a estação eleita 
\ref{sec:conceitoeleicaocoordenador}.

Ao término da construção de varal, cada nó no mesmo, acumula as funções de coordenador e 
proprietário de um anel unitário. Essas funções somente mudarão para possivelmente dois 
nós diferentes quando o ``proprietário e coordenador'' inicial não estiver presente,
ou quando houver eleição no anel.

%Gerenciamento de vários \textit{tokens}
Uma vez que o nosso protocolo implementa vários \textit{tokens} e qualquer nó pode gerar um \textit{token},
são necessários procedimentos para eliminar \textit{tokens} quando não têm mais utilidade. Para lidar com
a eliminação de \textit{tokens} atribuimos prioridades a \textit{tokens}. Definimos a prioridade de um \textit{token} como
sendo Cnt\_Gen desse \textit{token}. Isto é, quando um \textit{token} completa a rotação voltando ao proprietário,
a sua prioridade é incrementada. Caso dois \textit{tokens} tenham prioridades iguais, os endereços 
RA deles são usados para escolher que \textit{token} eliminar. A prioridade de um nó é a prioridade do
último \textit{token} que este nó aceitou ou gerou. Se um nó receber um \textit{token} com prioridade inferior a
dele, este nó elimina o \textit{token} sem aceitá-lo e avisa ao seu predecessor. Assim, o predecessor não
vai monitorar esse \textit{token}.

\section{Tratamento de falhas}
Um nó simples é considerado em falha, se o predecessor dele não receber um \emph{AckI} após
um determinado número de tentativas de transmissões de \textit{token}. E, se algum nó, exceto o 
proprietário, receber um \textit{token} com o Cnt\_Gen igual ao seu Cnt\_Gen, então este nó assume que
o proprietário está em falha.

%RECUPERAÇÃO AS FALHAS
O nosso protocolo implementa mecanismos para recuperar as falhas
causadas por quedas inesperadas de nós. A seguir, descrevemos
as estratégias adotadas:
\begin{itemize}
\item se o predecessor de um nó simples identificar a falha do nó, então este predecessor
busca na sua tabela de conectividade (em ordem de transmissão de \textit{token}) um nó para
fechar o anel. Essa reconstrução deve ser feita de modo que o anel seja reconstruído
reduzindo menor número de nós possível~\cite{ergenthesis}.
\item a queda inesperada de um coordenador causará rutura em varal e em anel. Neste
caso, teremos dois componentes isolados: predecessor no varal do coordenador em
falha busca um nó viável para fechar o varal (usando as estratégias explicadas no item
anterior); também, o predecessor no anel cujo coordenador falhou busca um nó na sua tabela
de conectividade para fechar o anel (usando as estratégias explicadas no item anterior).
Um nó \textrm{N} no anel onde o coordenador falhou vai receber o \textit{token} com Cnt\_Coord
desatualizado, então ele assume que o coordenador não está presente. Logo, este nó \textrm{N} verifica se
consegue escutar algum nó no varal olhando a sua tabela 3 (veja figura \ref{fig:alcance}). Se 
ele consegue escutar pelo menos um nó no varal, ele vai fazer \textit{broadcast} solicitando a entrada no
varal. E, se for introduzido, ele vai alterar Cnt\_Coord e assumir o papel de coordenador.
Porém, se não for introduzido, ele passa o \textit{token} a diante e o sucessor dele vai tentar
o mesmo procedimento, e assim sucessivamente até que algum nó no anel consiga ser coordenador; ou,
até que o varal fique inalcançável para todos os nós no anel isolado.

\item se um nó receber \textit{token} com Cnt\_Gen desatualizado, este \textit{token} assume que o 
proprietário não está presente. Então, ele inicia as eleições para encontrar um proprietário.
\end{itemize}

%Inclusão de nós aos anéis
\section{Procedimentos de entrada e saída}
\subsection{Procedimento de entrada}
\label{sec:procedimentoentrada}

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{in-no-simples-v2.pdf}
\caption{Entrada do nó R no anel D}
\label{fig:innode}
\end{figure}

Um nó $X$ faz \textit{broadcast} solicitando entrada em um anel. Para cada nó $Y$ no anel
que escutar (o \textit{broadcast}), espera receber \textit{token} e verifica se a capacidade
máxima do anel não foi atingida, se não foi atingida, então envia uma mensagem
contendo ID dele e ID do $Succ_{Y}$ ao nó $X$. Depois, o nó $Y$ fica aguardando uma mensagem
``Atribuir sucessor'' vinda do nó $X$. Para que essa mensagem chegue a $Y$, $X$ terá que enviar
``Atribuir predecessor'' para $Succ_{Y}$ e receber deste último ``Atribuir sucessor''.
Quando $Y$ receber ``Atribuir sucessor'' vinda do $X$, ele enviará uma mensagem
``Atribuir predecessor'' como resposta ao $X$. Assim, o nó $X$ é incluído no anel como
sucessor do $Y$ e predecessor do $Succ_{Y}$. No entanto, se $X$ não receber 
``Atribuir sucessor'' do $Succ_{Y}$ até expirar o tempo de espera, ele enviará
``Atribuir predecessor'' para $Y$. Este último responderá com uma mensagem
``Atribuir sucessor'', se ainda for possível criar um novo anel. Se não for possível, o nó
$Y$ passará o \textit{token} para que outro nó tente incluir o $X$. Se nenhum nó $Y$
no anel consegue introduzir o nó $X$, ou se o número de tentativas de solicitar entrada 
(através de \textit{broadcast}) atingir o máximo, o nó X vai construir um anel unitário e 
aguardar por tempo $\alpha$ antes de executar o procedimento de entrada novamente.


Na figura \ref{fig:innode} apresentamos um exemplo do procedimento de entrada.
Inicialmente, o nó R faz \textit{broadcast} solicitando entrada. O nó D no anel D
escuta \textit{broadcast}, então espera receber o \textit{token}, daí envia o ID dele e ID
do sucessor dele (L) ao nó R. Logo, o nó R envia uma mensagem 
``Atribuir predecessor'' ao L que recebe a mensagem e envia ``Atribuir sucessor'' para R. Logo
que o nó R receber a mensagem do L, ele vai enviar ``Atribuir sucessor'' para o D, e este último
envia ``Atribuir predecessor'' para o nó R (após ter recebido a mensagem do R).


\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{in-ring-varal-v2.pdf}
\caption{Inclusão do anel V ao varal P}
\label{fig:inringvaral}
\end{figure}

O procedimento de entrada de um anel em um varal é ligeiramente diferente. Se algum nó 
$N$ no anel isolado consegue escutar as transmissões feitas em varal, ele 
espera receber o \textit{token}, confirma ausência de coordenador (através de Coord\_Cnt);
então, ele faz \textit{broadcast} solicitando entrada no
varal. Se algum coordenador $Y$ no varal escutar o \textit{broadcast}, 
ele espera receber o \textit{token} do varal, verifica se a capacidade máxima do varal
ainda não foi atingida; se ainda houver alguma vaga no varal, então o nó $Y$
envia uma mensagem contendo ID dele e ID do $Succ_{Y}$ (no varal) para o nó $N$.
Quando o nó $N$ receber a mensagem do coordenador $Y$, ele envia uma
mensagem ``Atribuir predecessor'' para $Succ_{Y}$ (no varal). E,
espera receber do sucessor referido uma mensagem ``Atribuir sucessor''.
Depois de receber a mensagem do $Succ_{Y}$, ele envia uma
mensagem ``Atribuir sucessor'' para o nó $Y$ e este último envia para ele
(nó solicitante) uma mensagem ``Atribuir predecessor''. Daí termina o procedimento de
entrada do nó solicitante no varal.
Se o nó $N$ não receber resposta do $Succ_{Y}$, então
o coordenador $Y$ passará o \textit{token} para o $Succ_{Y}$ (no varal) tentar o
procedimento de entrada para o nó $N$. Se nenhum nó coordenador
no varal consegue introduzir o solicitante, então este último vai aguardar até que haja
nova oportunidade de tentar a entrada no varal.

Um exemplo do procedimento de entrada de um anel em um varal é apresentado na figura
\ref{fig:inringvaral}. O nó R no anel V faz \textit{broadcast} solicitando a entrada
no varal P. O nó T (atendente) escuta esse \textit{broadcast}, envia o ID dele e o ID do
sucessor dele para R. Este último nó envia uma mensagem ``Atribuir predecessor'' para o
nó M(sucessor do atendente no varal). Quando o nó M receber a mensagem do R, ele vai
responder enviando ``Atribuir sucessor''. E, o nó R envia ``Atribuir sucessor'' para o
nó T, após ter recebido a mensagem do nó M. Finalmente, o nó T envia uma mensagem 
``Atribuir predecessor'' para o solicitante R.

%\underline{\textbf{Observação:}}

\subsection{Procedimento de saída}
\label{sec:procedimentosaida}
\begin{enumerate}
 
\item \textbf{Nó simples}

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.35]{ring-node-leaving.pdf} %{out-no-simple.pdf}
\caption{Saída do nó A do anel R e coordenador T}
\label{fig:outnosimples}
\end{figure}

O nó cessante $X$ envia um pacote ``Atribuir sucessor'' com identificador do $Succ_{X}$ para
o $Pred_{X}$. Se $Pred_{X}$ consegue escutar o $Succ_{X}$, então $Pred_{X}$ envia
``Atribuir predecessor'' para $Succ_{X}$ e recebe ``Atribuir sucessor'' deste último . Se
$Pred_{X}$ não consegue escutar $Succ_{X}$,
então $Pred_{X}$ busca na sua tabela de conectividade um nó $N$, envia ``Atribuir predecessor''
para $N$ e recebe ``Atribuir sucessor'' do $N$.

A figura \ref{fig:outnosimples} ilustra uma situação em que o nó A inicia o procedimento
de saída enviando uma mensagem ``Atribuir sucessor'' (contendo identificador de S) para nó R.
E, o nó R envia uma mensagem ``Atribuir predecessor'' (contendo identificador) dele para S e
recebe ``Atribuir sucessor'' deste último.

\item \textbf{Nó proprietário}

Se o proprietário cessante forma um anel pendurado a varal e com dois nós, então ele executa o
procedimento de saída explicado no item 1 considerando o vizinho (predecessor e sucessor) no
seu varal. Se ele for um nó simples em um anel, por exemplo nó R na figura \ref{fig:outnosimples},
ele executa também o procedimento de saída explicado no item 1 mandando ``Atribuir sucessor''
com identificador do sucessor dele para o predecessor dele. E, este último espera receber o
\textit{token} e inicia eleições para encontrar um novo proprietário do anel. O vencedor dessas
eleições atribui o endereço dele ao campo RA do \textit{token}.

\item \textbf{Nó coordenador}

Seguindo a ilustração \ref{fig:coordexit}. O nó cessante (E) faz um \textit{broadcast}
para o anel dele avisando que vai sair. Na mensagem de \textit{broadcast} ele coloca
os endereços do predecessor (A) e sucessor (C) dele no varal. Se um nó (digamos S) no anel
(N), onde (E) é coordenador, escutar o \textit{broadcast}, ele verifica se consegue escutar
predecessor (A) e sucessor (C) do coordenador (E) no varal. Se consegue escutá-los, então espera
receber \textit{token} de permissão no anel (N), envia uma mensagem ``Atribuir predecessor'' para
o sucessor (C) no varal (e, recebe deste último ``Atribuir sucessor''), e envia uma mensagem
``Atribuir sucessor'' para o predecessor (A) no varal (e, recebe do A um ``Atribuir predecessor'').
Ainda, o coordenador cessante envia uma mensagem ``Atribuir sucessor'' contendo
identificador do sucessor (N) para o predecessor (Q). E, esse predecessor (Q) envia uma
mensagem ``Atribuir predecessor'' para o sucessor (N).

Se o coordenador cessante for proprietário de um anel não unitário, então ele
primeiramente faz um \textit{broadcast} avisando que quer sair. Se o nó que estiver com
o \textit{token} escutar o \textit{broadcast}, então ele imediatamente inicia as eleições para
encontrar um novo proprietário. O vencedor dessas eleições atribui endereço dele ao campo RA do
\textit{token}. Uma vez que o nó se desfez de encargo de proprietário, ele pode executar
o procedimento de saída para um nó coordenador.

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{coord-exit.pdf}
\caption{Saída do coordenador E}
\label{fig:coordexit}
\end{figure}

\item \textbf{Nó proprietário de varal}

O nó proprietário cessante espera receber o \textit{token} e convoca as eleições 
enviando uma mensagem para o sucessor dele no varal. Todos os nós no varal vão
participar das eleições para encontrar um novo proprietário do varal. Uma vez
encontrado um novo proprietário, este atribui o endereço dele ao campo RA do varal. A
mudança de papel do nó cessante de proprietário do varal para um coordenador, permite
a ele executar o procedimento de saída para um coordenador explicado no item 2.

\end{enumerate}



\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{reconexao-de-anel.pdf}
\caption{Reconexão do anel após a saída do nó E}
\label{fig:reconexao}
\end{figure}

\underline{Importante:} O processo de fechar um anel requer tratamento de um caso
particular. Para explicar esse caso e apresentar a solução adotada por nós, usamos o
exemplo da figura \ref{fig:reconexao}. Imagine que o nó E decide sair, ele envia uma mensagem 
``Atribuir sucessor'' para C. Então, o nó C busca na tabela de conectividade um nó para fechar
 o anel. Uma vez que o nó C não consegue escutar os nós G, I, K e M, e consegue
escutar o nó O, então ele vai fechar o anel com este nó O figura \ref{fig:reconexao} 2). 
O trecho que vai do nó G a M fica fora do anel. Após algum tempo, o nó G constata que não está
recebendo o \textit{token}, então solicita o sucessor I para formarem um anel. Consequentemente,
o nó I deixa de ser predecessor do K. Por sua vez, o K também verifica que não está
recebendo o \textit{token}, então solicita o sucessor M para formarem um outro anel 3). Se o
trecho tivesse um número ímpar de nós, último nó desse trecho formaria um anel
unitário. Essa solução é aplicada sempre que um nó sai de anel ou falha.

\subsubsection{Transformação de um anel em varal}
\label{sec:transanelemvaral}
Se um nó não coordenador em um anel não unitário receber uma solicitação para formar um novo
anel, ele forma o novo anel e assume papel de coordenador e proprietário no mesmo. Depois, 
ele espera receber \textit{token}, verifica se este último já foi transformado em \textit{token}
de varal:
\begin{itemize}
 \item Se sim, ele faz o que tem a fazer com o \textit{token} e passa para o sucessor dele
 \item Se não, ele transforma o \textit{token} em \textit{token} de varal e assume o papel de proprietário
\end{itemize}

Se o proprietário de um anel não unitário receber \textit{token} e verificar que a capacidade
máxima do mesmo foi atingida, ele transforma o \textit{token} em \textit{token} de varal e continua
sendo proprietário.

\underline{\textbf{Observação:}} Por simplicidade, se o número de nós em um varal diminuir até 1,
esse varal é transformado em anel.